/*
提交链接：https://leetcode.cn/problems/accounts-merge/submissions/573559355
721. 账户合并-中等
完成日期：2024/10/17
并查集
*/

class UnionFind {
public:
    UnionFind() {}
    void add(const string& email) {
        if (parent.find(email) == parent.end()) {
            parent[email] = email; // 每个邮箱的父节点初始为自己
        }
    }
    string find(const string& email) {
        if (parent[email] != email) {
            parent[email] = find(parent[email]); // 路径压缩
        }
        return parent[email];
    }
    // 合并两个邮箱
    void unionSet(const string& email1, const string& email2) {
        string root1 = find(email1);
        string root2 = find(email2);
        if (root1 != root2) {
            parent[root1] = root2; // 合并两个根节点
        }
    }
private:
    unordered_map<string, string> parent; // 存储每个邮箱的父节点
};
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        UnionFind uf;
        unordered_map<string, string> emailToName; // 记录邮箱对应的姓名
        // 步骤1: 添加邮箱到并查集中，并建立邮箱与姓名的映射
        for (const auto& account : accounts) {
            string name = account[0]; // 获取账户名
            for (int i = 1; i < account.size(); ++i) {
                string email = account[i];
                uf.add(email); // 添加邮箱
                emailToName[email] = name; // 映射邮箱到姓名
                if (i > 1) {
                    uf.unionSet(account[i], account[i - 1]); // 合并当前邮箱与前一个邮箱
                }
            }
        }
        // 步骤2: 按根节点收集邮箱
        unordered_map<string, vector<string>> mergedAccounts;
        for (const auto& [email, _] : emailToName) {
            string root = uf.find(email); // 找到邮箱的根节点
            mergedAccounts[root].push_back(email); // 将邮箱添加到对应的根节点下
        }
        // 步骤3: 准备结果
        vector<vector<string>> result;
        for (const auto& [root, emails] : mergedAccounts) {
            vector<string> account = { emailToName[root] }; // 获取姓名
            vector<string> emailList = emails; // 获取邮箱列表
            sort(emailList.begin(), emailList.end()); // 按字母顺序排序
            account.insert(account.end(), emailList.begin(), emailList.end()); // 合并姓名和邮箱列表
            result.push_back(account); // 将合并后的账户添加到结果中
        }
        return result; // 返回最终结果
    }
};